package week2.blog_code.exer1000;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        System.out.println(partition(arr, 0, n - 1, k));
    }

    /**
     * 在数组arr的[left, right]区域找到第k小的数并返回
     * @return 第k小的数
     */
    private static int partition(int[] arr, int left, int right, int k) {
        // 选基准元素
        int pivot = arr[right];
        int prev = left - 1; // 指向小于pivot的最后元素
        int cur = left; // 遍历数组
        while (cur <= right) {
            if (arr[cur] <= pivot) {
                // 将小于等于pivot的元素移至前面
                int tmp = arr[prev + 1];
                arr[prev + 1] = arr[cur];
                arr[cur] = tmp;
                cur++;
                prev++;
            } else {
                // 大于pivot不用移动
                cur++;
            }
        }
        int leftNum = prev - left; // 左半区域元素个数
        if (leftNum + 1 == k) {
            return pivot;
        } else if (leftNum + 1 > k) {
            // 递归左半区域
            return partition(arr, left, prev - 1, k);
        } else {
            // 递归右半区域
            return partition(arr, prev + 1, right, k - (leftNum + 1));
        }
    }
}
